class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int last_day = days.back();
        unordered_set<int> day_set(days.begin(), days.end());
        vector<int> f(last_day + 1);
        for (int i = 1; i <= last_day; i++) {
            if (!day_set.contains(i)) {
                f[i] = f[i - 1];
            }
            else {
                f[i] = min({ f[i - 1] + costs[0],
                            f[max(i - 7, 0)] + costs[1],
                            f[max(i - 30, 0)] + costs[2] });
            }
        }
        return f[last_day];
    }
};